// 版权所有2009 Go作者。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 信号量实现公开给Go。
// 预期用途是提供一个睡眠和唤醒
// 原语，可用于其他同步原语的争用情况
// 中。
// 因此它的目标与Linux的futex相同，但它的语义要简单得多。
// 
// 也就是说，不要将这些视为信号量。
// 将其视为实现睡眠和唤醒的一种方式
// 这样，每一次睡眠都会伴随一次唤醒，
// 即使由于种族原因，唤醒发生在睡眠之前。
// 
// 参见Mullender和Cox，“计划9中的信号量”，
// https:

package runtime

import (
	"internal/cpu"
	"runtime/internal/atomic"
	"unsafe"
)

// sync.Mutex的异步信号量。

// semaRoot拥有一个具有不同地址（s.elem）的sudog平衡树。
// 这些sudog中的每一个都可以依次指向（通过s.waitlink）等待同一地址的其他sudog的列表
// 。
// 相同地址的sudogs内部列表上的操作
// 都是O（1）。顶级semaRoot列表的扫描是O（log n），
// 其中n是具有被阻止的goroutine 
// 的不同地址的数量，这些地址散列到给定的semaRoot。
// 在我们引入第二级列表之前，请参见golang.org/issue/17953了解一个工作不好的程序
// 以及test/locklinear.go 
// 了解一个测试。
type semaRoot struct {
	lock  mutex
	treap *sudog // 唯一服务员平衡树的根。
	nwait uint32 // 服务员人数。在没有锁的情况下读取。
}

// Prime不与任何用户模式关联。
const semTabSize = 251

var semtable [semTabSize]struct {
	root semaRoot
	pad  [cpu.CacheLinePadSize - unsafe.Sizeof(semaRoot{})]byte
}

// go:linkname-sync\u-runtime\u-Semacquire-sync.runtime\u-Semacquire-
func sync_runtime_Semacquire(addr *uint32) {
	semacquire1(addr, false, semaBlockProfile, 0)
}

// go:linkname-poll\u-runtime\u-Semacquire-internal/poll.runtime\u-Semacquire-
func poll_runtime_Semacquire(addr *uint32) {
	semacquire1(addr, false, semaBlockProfile, 0)
}

func sync_runtime_Semrelease(addr *uint32, handoff bool, skipframes int) {
	semrelease1(addr, handoff, skipframes)
}

func sync_runtime_SemacquireMutex(addr *uint32, lifo bool, skipframes int) {
	semacquire1(addr, lifo, semaBlockProfile|semaMutexProfile, skipframes)
}

// go:linkname poll\u runtime\u Semrelease internal/poll.runtime\u Semrelease 
func poll_runtime_Semrelease(addr *uint32) {
	semrelease(addr)
}

func readyWithTime(s *sudog, traceskip int) {
	if s.releasetime != 0 {
		s.releasetime = cputicks()
	}
	goready(s.g, traceskip)
}

type semaProfileFlags int

const (
	semaBlockProfile semaProfileFlags = 1 << iota
	semaMutexProfile
)

// 从运行时调用。
func semacquire(addr *uint32) {
	semacquire1(addr, false, 0, 0)
}

func semacquire1(addr *uint32, lifo bool, profile semaProfileFlags, skipframes int) {
	gp := getg()
	if gp != gp.m.curg {
		throw("semacquire not on the G stack")
	}

	// 简单的案例。
	if cansemacquire(addr) {
		return
	}

	// 更难的情况：
	// 递增侍者计数
	// 再次尝试CansAcquire，如果成功返回
	// 将自己作为侍者排队
	// 睡眠
	// （侍者描述符由信号器出列）
	s := acquireSudog()
	root := semroot(addr)
	t0 := int64(0)
	s.releasetime = 0
	s.acquiretime = 0
	s.ticket = 0
	if profile&semaBlockProfile != 0 && blockprofilerate > 0 {
		t0 = cputicks()
		s.releasetime = -1
	}
	if profile&semaMutexProfile != 0 && mutexprofilerate > 0 {
		if t0 == 0 {
			t0 = cputicks()
		}
		s.acquiretime = t0
	}
	for {
		lockWithRank(&root.lock, lockRankRoot)
		// 将我们自己添加到nwait以禁用semrelease中的“easy case”。
		atomic.Xadd(&root.nwait, 1)
		// 检查cansemacquire以避免错过唤醒。
		if cansemacquire(addr) {
			atomic.Xadd(&root.nwait, -1)
			unlock(&root.lock)
			break
		}
		// cansemacquire知道我们正在等待后的任何释放
		// （我们在上面设置了nwait），所以去睡觉吧。
		root.queue(addr, s, lifo)
		goparkunlock(&root.lock, waitReasonSemacquire, traceEvGoBlockSync, 4+skipframes)
		if s.ticket != 0 || cansemacquire(addr) {
			break
		}
	}
	if s.releasetime > 0 {
		blockevent(s.releasetime-t0, 3+skipframes)
	}
	releaseSudog(s)
}

func semrelease(addr *uint32) {
	semrelease1(addr, false, 0)
}

func semrelease1(addr *uint32, handoff bool, skipframes int) {
	root := semroot(addr)
	atomic.Xadd(addr, 1)

	// 简单的例子：没有服务员？
	// 此检查必须在xadd之后进行，以避免错过唤醒
	// （请参阅semacquire中的循环）。
	if atomic.Load(&root.nwait) == 0 {
		return
	}

	// 更难的情况是：找一个服务员，然后叫醒他。
	lockWithRank(&root.lock, lockRankRoot)
	if atomic.Load(&root.nwait) == 0 {
		// 该计数已被另一个goroutine使用，
		// 因此无需唤醒另一个goroutine。
		unlock(&root.lock)
		return
	}
	s, t0 := root.dequeue(addr)
	if s != nil {
		atomic.Xadd(&root.nwait, -1)
	}
	unlock(&root.lock)
	if s != nil { // 可能会很慢，甚至会屈服，因此先解锁
		acquiretime := s.acquiretime
		if acquiretime != 0 {
			mutexevent(t0-acquiretime, 3+skipframes)
		}
		if s.ticket != 0 {
			throw("corrupted semaphore ticket")
		}
		if handoff && cansemacquire(addr) {
			s.ticket = 1
		}
		readyWithTime(s, 5+skipframes)
		if s.ticket == 1 && getg().m.locks == 0 {
			// 直接G切换
			// 准备就绪，时间已在
			// 当前P中添加了下一个运行的服务者G；现在我们调用调度程序，以便立即开始运行
			// 服务生。
			// 注意，服务员继承了我们的时间片：这是理想的
			// 以避免一个高度竞争的信号量无限期地占用P 
			// 的时间。goyield与Gosched类似，但它会发出一个
			// “抢占”跟踪事件，更重要的是，将
			// /当前G放在本地runq上，而不是全局runq上。
			// 我们只在饥饿状态下（handoff=true）这样做，就像在非饥饿状态下一样，不同的服务员可能在我们屈服/调度时获取信号量，这是浪费。我们等待着进入饥饿的政权，然后我们开始直接交接票和票。
			goyield()
		}
	}
}

func semroot(addr *uint32) *semaRoot {
	return &semtable[(uintptr(unsafe.Pointer(addr))>>3)%semTabSize].root
}

func cansemacquire(addr *uint32) bool {
	for {
		v := atomic.Load(addr)
		if v == 0 {
			return false
		}
		if atomic.Cas(addr, v, v-1) {
			return true
		}
	}
}

// 队列将s添加到semaRoot中被阻止的goroutine中。
func (root *semaRoot) queue(addr *uint32, s *sudog, lifo bool) {
	s.g = getg()
	s.elem = unsafe.Pointer(addr)
	s.next = nil
	s.prev = nil

	var last *sudog
	pt := &root.treap
	for t := *pt; t != nil; t = *pt {
		if t.elem == unsafe.Pointer(addr) {
			// 列表中已有地址。
			if lifo {
				// 在treap中用s代替t。
				*pt = s
				s.ticket = t.ticket
				s.acquiretime = t.acquiretime
				s.parent = t.parent
				s.prev = t.prev
				s.next = t.next
				if s.prev != nil {
					s.prev.parent = s
				}
				if s.next != nil {
					s.next.parent = s
				}
				// 在s的等待列表中首先添加t。
				s.waitlink = t
				s.waittail = t.waittail
				if s.waittail == nil {
					s.waittail = t
				}
				t.parent = nil
				t.prev = nil
				t.next = nil
				t.waittail = nil
			} else {
				// 将s添加到t的等待列表的末尾。
				if t.waittail == nil {
					t.waitlink = s
				} else {
					t.waittail.waitlink = s
				}
				t.waittail = s
				s.waitlink = nil
			}
			return
		}
		last = t
		if uintptr(unsafe.Pointer(addr)) < uintptr(t.elem) {
			pt = &t.prev
		} else {
			pt = &t.next
		}
	}

	// 将s作为新叶添加到唯一地址树中。
	// 平衡树是一个使用票证作为随机堆优先级的treap。
	// 也就是说，它是一个根据元素地址排序的二叉树，
	// 但是在关于这些
	// 地址的可能二叉树空间中，通过在ticket:s.ticket<=s.prev.ticket和s.next.ticket上保持堆排序
	// 来保持平均平衡。
	// https:
	// https:
	// 
	// s.ticket在两个位置与零比较，因此设置最低位。
	// 不会显著影响treap的质量。
	s.ticket = fastrand() | 1
	s.parent = last
	*pt = s

	// 根据票据（优先级）向上旋转到树中。
	for s.parent != nil && s.parent.ticket > s.ticket {
		if s.parent.prev == s {
			root.rotateRight(s.parent)
		} else {
			if s.parent.next != s {
				panic("semaRoot queue")
			}
			root.rotateLeft(s.parent)
		}
	}
}

// 出列在addr上阻止的semaRoot中搜索并找到第一个goroutine 
// 。
// 如果正在分析sudog，则dequeue返回它现在被唤醒的时间
// 。否则现在是0。
func (root *semaRoot) dequeue(addr *uint32) (found *sudog, now int64) {
	ps := &root.treap
	s := *ps
	for ; s != nil; s = *ps {
		if s.elem == unsafe.Pointer(addr) {
			goto Found
		}
		if uintptr(unsafe.Pointer(addr)) < uintptr(s.elem) {
			ps = &s.prev
		} else {
			ps = &s.next
		}
	}
	return nil, 0

Found:
	now = int64(0)
	if s.acquiretime != 0 {
		now = cputicks()
	}
	if t := s.waitlink; t != nil {
		// 将同样等待addr的t替换为唯一addr的根树中的s。
		*ps = t
		t.ticket = s.ticket
		t.parent = s.parent
		t.prev = s.prev
		if t.prev != nil {
			t.prev.parent = t
		}
		t.next = s.next
		if t.next != nil {
			t.next.parent = t
		}
		if t.waitlink != nil {
			t.waittail = s.waittail
		} else {
			t.waittail = nil
		}
		t.acquiretime = now
		s.waitlink = nil
		s.waittail = nil
	} else {
		// 根据优先顺序，向下旋转s，使其成为树叶，以便移除。
		for s.next != nil || s.prev != nil {
			if s.next == nil || s.prev != nil && s.prev.ticket < s.next.ticket {
				root.rotateRight(s)
			} else {
				root.rotateLeft(s)
			}
		}
		// 删除s，现在是一片叶子。
		if s.parent != nil {
			if s.parent.prev == s {
				s.parent.prev = nil
			} else {
				s.parent.next = nil
			}
		} else {
			root.treap = nil
		}
	}
	s.parent = nil
	s.elem = nil
	s.next = nil
	s.prev = nil
	s.ticket = 0
	return s, now
}

// rotateLeft旋转以节点x为根的树。
// 将（xa（ybc））转换为（xab）c）。
func (root *semaRoot) rotateLeft(x *sudog) {
	// p->（xa（ybc））
	p := x.parent
	y := x.next
	b := y.prev

	y.prev = x
	x.parent = y
	x.next = b
	if b != nil {
		b.parent = x
	}

	y.parent = p
	if p == nil {
		root.treap = y
	} else if p.prev == x {
		p.prev = y
	} else {
		if p.next != x {
			throw("semaRoot rotateLeft")
		}
		p.next = y
	}
}

// rotateRight旋转以节点y为根的树。
// 将（y（xab）c）转换为（xa（ybc））。
func (root *semaRoot) rotateRight(y *sudog) {
	// p->（y（x a b）c）
	p := y.parent
	x := y.prev
	b := x.next

	x.next = y
	y.parent = x
	y.prev = b
	if b != nil {
		b.parent = y
	}

	x.parent = p
	if p == nil {
		root.treap = x
	} else if p.prev == y {
		p.prev = x
	} else {
		if p.next != y {
			throw("semaRoot rotateRight")
		}
		p.next = x
	}
}

// notifyList是一个基于票据的通知列表，用于实现sync.Cond。
// 
// 必须与同步包保持同步。
type notifyList struct {
	// 等待是下一位服务员的票号。它在原子上
	// 在锁外递增。
	wait uint32

	// notify是下一个要通知的服务员的票号。它可以
	// 在锁外读取，但只能在持有锁的情况下写入。
	// 
	// 等待和通知都可以结束，只要它们的“未结束”差异在2^31的范围内，就可以正确处理此类情况。
	// 如果不是这样，我们需要在同一个条件下阻止2^31+个goroutines 
	// 这目前是不可能的。
	notify uint32

	// 停车服务员名单。
	lock mutex
	head *sudog
	tail *sudog
}

// less检查a<b，考虑到a&b运行计数可能溢出
// 32位范围，并且它们的“未包装”差始终小于2^31。
func less(a, b uint32) bool {
	return int32(a-b) < 0
}

// notifyListAdd将调用者添加到通知列表中，以便它可以接收
// 通知。调用方最终必须调用notifyListWait来等待
// 这样的通知，并传递返回的票证号。
// go:linkname notifyListAdd sync.runtime\u notifyListAdd 
func notifyListAdd(l *notifyList) uint32 {
	// 例如，当从
	// sync.Cond.Wait调用时，在读取模式下保持RWMutex时，可以同时调用此函数。
	return atomic.Xadd(&l.wait, 1) - 1
}

// notifyListWait等待通知。如果在调用
// notifyListAdd之后发送了一个，它将立即返回。否则，它会阻塞。
// 转到：linkname notifyListWait sync.runtime\u notifyListWait 
func notifyListWait(l *notifyList, t uint32) {
	lockWithRank(&l.lock, lockRankNotifyList)

	// 如果已通知此票证，请立即返回。
	if less(t, l.notify) {
		unlock(&l.lock)
		return
	}

	// 排队。
	s := acquireSudog()
	s.g = getg()
	s.ticket = t
	s.releasetime = 0
	t0 := int64(0)
	if blockprofilerate > 0 {
		t0 = cputicks()
		s.releasetime = -1
	}
	if l.tail == nil {
		l.head = s
	} else {
		l.tail.next = s
	}
	l.tail = s
	goparkunlock(&l.lock, waitReasonSyncCondWait, traceEvGoBlockCond, 3)
	if t0 != 0 {
		blockevent(s.releasetime-t0, 2)
	}
	releaseSudog(s)
}

// notifyListNotifyAll通知列表中的所有条目。
// go:linkname notifyListNotifyAll sync.runtime\u notifyListNotifyAll 
func notifyListNotifyAll(l *notifyList) {
	// 快速路径：如果自上次通知以来没有新的等待程序
	// 我们不需要获取锁。
	if atomic.Load(&l.wait) == atomic.Load(&l.notify) {
		return
	}

	// 将列表拉出到局部变量中，等待者将准备好
	// 锁外。
	lockWithRank(&l.lock, lockRankNotifyList)
	s := l.head
	l.head = nil
	l.tail = nil

	// 更新要通知的下一张票据。我们可以将其设置为wait的当前值
	// 因为以前的任何等待者都已经在列表中
	// 或者在尝试将自己添加到列表时会注意到他们已经收到通知。
	atomic.Store(&l.notify, atomic.Load(&l.wait))
	unlock(&l.lock)

	// 检查一下当地的名单，让所有服务员做好准备。
	for s != nil {
		next := s.next
		s.next = nil
		readyWithTime(s, 4)
		s = next
	}
}

// notifyListNotifyOne通知列表中的一个条目。
// go:linkname notifyListNotifyOne sync.runtime\u notifyListNotifyOne 
func notifyListNotifyOne(l *notifyList) {
	// 快速路径：如果上次通知后没有新的等待程序
	// 我们根本不需要获取锁。
	if atomic.Load(&l.wait) == atomic.Load(&l.notify) {
		return
	}

	lockWithRank(&l.lock, lockRankNotifyList)

	// 如果我们需要做任何事情，请在锁下重新检查。
	t := l.notify
	if t == atomic.Load(&l.wait) {
		unlock(&l.lock)
		return
	}

	// 更新下一个通知票号。
	atomic.Store(&l.notify, t+1)

	// 尝试查找需要通知的g。
	// 如果它还没有进入名单，我们就找不到它，
	// 但一旦看到新的通知号码，它就不会自动停车。
	// 
	// 此扫描看起来是线性的，但实际上总是很快停止。
	// 因为g的队列与取数分开，
	// 列表中可能会有一些小的重新排序，但我们
	// 希望我们要找的g靠近前面。
	// 在列表中，g的前面有其他人，只有到了
	// 的程度，它输掉了比赛，所以迭代不会太长。即使g不见了，这也适用：
	// 它还没有入睡，已经输给了
	// 我们在名单上找到的（少数）其他g。
	for p, s := (*sudog)(nil), l.head; s != nil; p, s = s, s.next {
		if s.ticket == t {
			n := s.next
			if p != nil {
				p.next = n
			} else {
				l.head = n
			}
			if n == nil {
				l.tail = p
			}
			unlock(&l.lock)
			s.next = nil
			readyWithTime(s, 4)
			return
		}
	}
	unlock(&l.lock)
}

// go:linkname notifyListCheck sync.runtime\u notifyListCheck 
func notifyListCheck(sz uintptr) {
	if sz != unsafe.Sizeof(notifyList{}) {
		print("runtime: bad notifyList size - sync=", sz, " runtime=", unsafe.Sizeof(notifyList{}), "\n")
		throw("bad notifyList size")
	}
}

// go:linkname sync\u nanotime sync.runtime\u nanotime 
func sync_nanotime() int64 {
	return nanotime()
}
